#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;

//void lazy(int p, ll v, int n) {
//	sum[p] += v * n;
//	la[p] += v;
//}
//
//void down(int p, int ln, int rn) {
//	if (la[p] != 0) {
//		lazy(2 * p, la[p], ln);
//		lazy(2 * p + 1, la[p], rn);
//		la[p] = 0;
//	}
//}
//
//void up(int p) {
//	sum[p] = sum[2 * p] + sum[2 * p + 1];
//}
//
//void build(int l, int r,int p) {
//	if (l == r) {
//		sum[p] = a[l];
//	}
//	else {
//		int m = (l + r) >> 1;
//		build(l, m, 2 * p);
//		build(m + 1, r, 2 * p + 1);
//		up(p);
//	}
//}
//
//
//ll query(int jobl, int jobr,int l,int r,int p) {
//	if (jobl <= l && r <= jobr) {
//		return sum[p];
//	}
//	else {
//		ll ans = 0;
//		int m = (l + r) >> 1;
//		down(p, m - l + 1, r - m);
//		if (jobl <= m)
//			ans += query(jobl, jobr, l, m, 2 * p);
//		if (jobr > m)
//			ans += query(jobl, jobr, m + 1, r, 2 * p + 1);
//		return ans;
//	}
//}
//
//void add(int jobl, int jobr, ll jobv, int l, int r, int p) {
//	if (jobl <= l && jobr >= r) {
//		lazy(p, jobv, r - l + 1);
//	}
//	else {
//		int m = (l + r) >> 1;
//		down(p, m - l + 1, r - m);
//		if (jobl <= m) {
//			add(jobl, jobr, jobv, l, m, 2 * p);
//		}
//		if (jobr > m) {
//			add(jobl, jobr, jobv, m + 1, r, 2 * p + 1);
//		}
//		up(p);
//	}
//}
//
//
//int n,k;
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> n >>k;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//	build(1, n, 1);
//	while (k--) {
//		int x;
//		cin >> x;
//		if (x == 1) {
//			int l, r, v;
//			cin >> l >> r >> v;
//			add(l, r, v, 1, n, 1);
//		}
//		else {
//			int l, r;
//			cin >> l >> r;
//			ll res = query(l, r, 1, n, 1);
//			cout << res << '\n';
//		}
//	}
//	return 0;
//}


//void lazy(int p, int v, int n) {
//	sum[p] = n * v;
//	la[p] = v;
//	update[p] = true;
//}
//
//void up(int p) {
//	sum[p] = sum[2 * p] + sum[2 * p + 1];
//}
//
//void down(int p, int ln, int rn) {
//	if (update[p]) {
//		update[p] = false;
//		lazy(2 * p, la[p], ln);
//		lazy(2 * p + 1, la[p], rn);
//		la[p] = 0;
//	}
//}
//
//void build(int l, int r, int p) {
//	if (l == r) {
//		sum[p] = a[l];
//	}
//	else {
//		int m = (l + r) >> 1;
//		build(l, m, 2 * p);
//		build(m + 1, r, 2 * p + 1);
//		up(p);
//	}
//	update[p] = false;
//}
//
//ll query(int jl, int jr, int l, int r, int p) {
//	if (jl == jr) {
//		return sum[p];
//	}
//	else {
//		ll ans = 0;
//		int m = (l + r) >> 1;
//		if (jl <= m) {
//			ans += query(jl, jr, l, m, 2 * p);
//		}
//		if (jr > m) {
//			ans += query(jl, jr, m + 1, r, 2 * p + 1);
//		}
//		return ans;
//	}
//}
//
//void sett(int jl, int jr,int jv ,int l, int r, int p) {
//	if (jl <= l && r <= jr) {
//		lazy(p, jv, r - l + 1);
//	}
//	else {
//		int m = (l + r) >> 1;
//		down(p, m - l + 1, r - m);
//		if (jl <= m) {
//			sett(jl, jr,jv, l, m, 2 * p);
//		}
//		if (jr > m) {
//			sett(jl, jr,jv, m + 1, r, 2 * p+1);
//		}
//		up(p);
//	}
//}
//


//int a[100005];
//ll mx[400005];
//ll la[400005];
//bool update[400005];
//
//void lazy(int p, int v) {
//	mx[p] += v;
//	la[p] += v;
//}
//
//void down(int p) {
//	if (la[p]) {
//		lazy(2 * p, la[p]);
//		lazy(2 * p + 1, la[p]);
//		la[p] = 0;
//	}
//}
//
//void up(int p) {
//	mx[p] = max(mx[2 * p], mx[2 * p + 1]);
//}
//
//void build(int l, int r, int p) {
//	if (l == r) {
//		mx[p] = a[l];
//	}
//	else {
//		int m = (l + r) >> 1;
//		build(l, m, 2 * p);
//		build(m + 1, r, 2 * p + 1);
//		up(p);
//	}
//}
//
//ll query(int jl, int jr, int l, int r, int p) {
//	if (jl <= l && jr <= r) {
//		return mx[p];
//	}
//	else {
//		down(p);
//		ll ans = 0; 
//		int m = (l + r) >> 1;
//		if (jl <= m) {
//			ans = max(query(jl, jr, l, m, 2 * p), ans);
//		}
//		if (jr > m) {
//			ans = max(query(jl, jr, m + 1, r, 2 * p + 1), ans);
//		}
//		return ans;
//	}
//}
//
//void add(int jl, int jr, int jv, int l, int r, int p) {
//	if (jl <= l && jr <= r) {
//		lazy(p, jv);
//	}
//	else {
//		down(p);
//		int m = (l + r) >> 1;
//		if (jl <= m) {
//			add(jl, jr, jv, l, m, 2 * p);
//		}
//		if (jr > m) {
//			add(jl, jr, jv, m + 1, r, 2 * p + 1);
//		}
//		up(p);
//	}
//}

//int a[100005];
//ll sum[400005];
//ll lad[400005];
//ll lac[400005];
//bool update[400005];
//
//void addlazy(int p, int v,int n) {
//	sum[p] += v*n;
//	lad[p] += v;
//}
//
//void changelazy(int p, int v, int n) {
//	sum[p] = n * v;
//	lad[p] = 0;
//	lac[p] = v;
//	update[p] = true;
//}
//
//void down(int p,int ln,int rn) {
//	if (update[p]) {
//		changelazy(2 * p, lac[p], ln);
//		changelazy(2 * p + 1, lac[p], rn);
//		update[p] = false;
//	}
//	if (lad[p]) {
//		addlazy(2 * p, lad[p], ln);
//		addlazy(2 * p + 1, lad[p], rn);
//		lad[p] = 0;
//	}
//}
//
//void up(int p) {
//	sum[p] = sum[2 * p]+ sum[2 * p + 1];
//}
//
//void build(int l, int r, int p) {
//	if (l == r) {
//		sum[p] = a[l];
//	}
//	else {
//		int m = (l + r) >> 1;
//		build(l, m, 2 * p);
//		build(m + 1, r, 2 * p + 1);
//		up(p);
//		update[p] = false;
//	}
//}
//
//void change(int jl, int jr, int jv, int l, int r, int p) {
//	if (jl <= l && jr >= r) {
//		changelazy(p, jv,r-l+1);
//	}
//	else {
//		int m = (l + r) >> 1;
//		down(p, m - l + 1, r - m);
//		if (jl <= m) {
//			change(jl, jr, jv, l, m, 2 * p);
//		}
//		if (jr > m) {
//			change(jl, jr, jv, m + 1, r, 2 * p + 1);
//		}
//		up(p);
//	}
//}
//
//void add(int jl, int jr, int jv, int l, int r, int p) {
//	if (jl <= l && jr >= r) {
//		addlazy(p, jv, r - l + 1);
//	}
//	else {
//		int m = (l + r) >> 1;
//		down(p, m - l + 1, r - m);
//		if (jl <= m) {
//			add(jl, jr, jv, l, m, 2 * p);
//		}
//		if (jr > m) {
//			add(jl, jr, jv, m + 1, r, 2 * p + 1);
//		}
//		up(p);
//	}
//}
//
//ll query(int jl, int jr, int l, int r, int p) {
//	if (jl <= l && jr >= r) {
//		return sum[p];
//	}
//	else {
//		ll ans = 0;
//		int m = (l + r) >> 1;
//		down(p, m - l + 1, r - m);
//		if (jl <= m) {
//			ans = max(ans, query(jl, jr, l, m, 2 * p));
//		}
//		if (jr > m) {
//			ans = max(ans, query(jl, jr, m + 1, r, 2 * p + 1));
//		}
//		return ans;
//	}
//}
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	
//
//	return 0;
//}

//int n, q;
//ll a[1000006];
//ll mx[4000006];
//bool update[4000006];
//ll lad[4000006];
//ll lac[4000006];
//const ll nul = 1e18;
//
//void up(int p) {
//	mx[p] = max(mx[2 * p], mx[2 * p + 1]);
//}
//
//void addlazy(int p, ll v) {
//	mx[p] += v;
//	lad[p] += v;
//}
//
//void changelazy(int p, ll v) {
//	mx[p] = v;
//	lad[p] = 0;
//	lac[p] = v;
//	update[p] = true;
//}
//
//void down(int p) {
//	if (update[p]) {
//		changelazy(2 * p, lac[p]);
//		changelazy(2 * p + 1, lac[p]);
//		update[p] = false;
//	}
//	if (lad[p]) {
//		addlazy(2 * p, lad[p]);
//		addlazy(2 * p + 1, lad[p]);
//		lad[p] = 0;
//	}
//}
//
//void build(int l, int r, int p) {
//	if (l == r) {
//		mx[p] = a[l];
//	}
//	else {
//		int m = (l + r) >> 1;
//		build(l, m, 2 * p);
//		build(m + 1, r, 2 * p + 1);
//		up(p);
//	}
//}
//
//void add(int jl, int jr, ll jv, int l, int r, int p) {
//	if (jl <= l && r <= jr) {
//		addlazy(p, jv);
//	}
//	else {
//		int m = (l + r) >> 1;
//		down(p);
//		if (jl <= m) {
//			add(jl, jr, jv, l, m, 2 * p);
//		}
//		if (jr > m) {
//			add(jl, jr, jv, m + 1, r, 2 * p + 1);
//		}
//		up(p);
//	}
//}
//
//void change(int jl, int jr, ll jv, int l, int r, int p) {
//	if (jl <= l && r <= jr) {
//		changelazy(p, jv);
//	}
//	else {
//		int m = (l + r) >> 1;
//		down(p);
//		if (jl <= m) {
//			change(jl, jr, jv, l, m, 2 * p);
//		}
//		if (jr > m) {
//			change(jl, jr, jv, m + 1, r, 2 * p + 1);
//		}
//		up(p);
//	}
//}
//
//ll query(int jl, int jr, int l, int r, int p) {
//	if (jl <= l && r <= jr) {
//		return mx[p];
//	}
//	else {
//		int m = (l + r) >> 1;
//		down(p);
//		ll ans = -1e18;
//		if (jl <= m) {
//			ans = max(ans, query(jl, jr, l, m, 2 * p));
//		}
//		if (jr > m) {
//			ans = max(ans, query(jl, jr, m + 1, r, 2 * p + 1));
//		}
//		return ans;
//	}
//}
//
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> n >> q;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//	build(1, n, 1);
//	for (int i = 1,op,jl,jr,jv; i <= q; i++) {
//		cin >> op;
//		if (op == 1) {
//			cin >> jl >> jr >> jv;
//			change(jl, jr, jv, 1, n, 1);
//		}
//		else if (op == 2) {
//			cin >> jl >> jr >> jv;
//			add(jl, jr, jv, 1, n, 1);	
//		}
//		else {
//			cin >> jl >> jr;
//			ll ans = query(jl, jr, 1, n, 1);
//			cout << ans << '\n';
//		}
//	}
//	return 0;
//}



//int t;
//string s;
//
//bool check(int m) {
//	vector<int> ok(26);
//	int n = s.size();
//	for (int i = 0; i < m; i++) {
//		ok[s[i] - 'a']++;
//	}
//	for (int i = 0; i < min(n / 2, n - m); i++) {
//		char c = s[n - i - 1];
//		if (i < m) {
//			ok[c - 'a']--;
//			if (ok[c - 'a'] < 0)
//				return false;
//		}
//		else {
//			if (s[i] != c)
//				return false;
//		}
//	}
//	return true;
//}
//
//void solve() {
//	cin >> s;
//	int l = 0, r = s.size() - 1;
//	while (l < r && s[l] == s[r]) {
//		l++;
//		r--;
//	}
//	s = s.substr(l, r - l + 1);
//	int ans = s.size();
//	for (int i = 0; i < 2; i++) {
//		l = 0, r = s.size();
//		while (l < r) {
//			int m = (l + r) >> 1;
//			if (check(m)) {
//				r = m;
//			}
//			else {
//				l = m + 1;
//			}
//		}
//		ans = min(ans, r);
//		reverse(s.begin(), s.end());
//	}
//	cout << ans << '\n';
//}
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}